#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:

    int rem[40];

    int tribonacci(int n) {
        return dfs(n);
    }

    int dfs(int d)
    {
        if (rem[d]) return rem[d];
        if (d == 0) return 0;
        else if (d == 1 || d == 2) return 1;
        if (rem[d - 1] == 0) rem[d - 1] = dfs(d - 1);
        if (rem[d - 2] == 0) rem[d - 2] = dfs(d - 2);
        if (rem[d - 3] == 0) rem[d - 3] = dfs(d - 3);
        return rem[d - 1] + rem[d - 2] + rem[d - 3];
    }
};

class Solution {
public:

    int dp[38];

    int tribonacci(int n) {
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        int tmp = 3;
        while (tmp <= n) {
            dp[tmp] = dp[tmp - 1] + dp[tmp - 2] + dp[tmp - 3];
            tmp++;
        }
        return dp[n];
    }
};

class Solution {
public:
    int waysToStep(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        long long a = 0, b = 1, c = 1, d = 2;
        for (int i = 2; i <= n; i++) {
            d = (a + b + c) % 1000000007;
            a = b; b = c; c = d;
        }
        return d;
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int len = cost.size();
        vector<int> dp(cost.size() + 1);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return min(dp[len - 1], dp[len - 2]);
    }
};
class Solution {
public:
    int numDecodings(string s) {
        int len = s.size();
        vector<int> dp(len + 1, 0);
        if (s[0] != '0') dp[0]++;
        if (dp[0] != 0) {
            if ((s[0] - '0') * 10 + (s[1] - '0') < 27)
                dp[1]++;
            if (s[1] != '0')
                dp[1]++;
        }

        for (int i = 2; i < len; i++) {
            if (s[i] != '0') dp[i] += dp[i - 1];
            if (s[i - 1] == '0');
            else if ((s[i - 1] - '0') * 10 + (s[i] - '0') < 27) {
                dp[i] += dp[i - 2];
            }
        }
        for (int i = 0; i < len; i++)
            cout << dp[i] << " ";
        return dp[len - 1];
    }
};

